package cn.edu.xjtu.work.validPalindrome;

/**
 * 680. 验证回文字符串 Ⅱ
 * 
 * 给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
 */
public class Solution {
    public static void main(String[] args) {
        Solution solu = new Solution();
        System.out.println(solu.validPalindrome(
                "aguokepatgbnvfqmgmlcupuufxoohdfpgjdmysgvhmvffcnqxjjxqncffvmhvgsymdjgpfdhooxfuupuculmgmqfvnbgtapekouga"));
    }

    public boolean validPalindrome(String s) {
        if (s == null) {
            return false;
        }
        if (s.length() < 3) {
            return true;
        }
        int len = s.length();
        int offset = 1;
        for (int i = 0; i < len / 2; i++) {
            if (s.charAt(i) == s.charAt(len - i - offset)) {
                continue;
            } else {
                return valid(s, i + 1, len - i - offset) || valid(s, i, len - i - offset - 1);
            }
        }
        return true;

    }

    public boolean valid(String s, int low, int high) {
        for (int i = low, j = high; i < j; ++i, --j) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }
        return true;
    }
}
